package LeetCode;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/*139. 单词拆分

        给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

        注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。



        示例 1：

        输入: s = "leetcode", wordDict = ["leet", "code"]
        输出: true
        解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
        示例 2：

        输入: s = "applepenapple", wordDict = ["apple", "pen"]
        输出: true
        解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
        注意，你可以重复使用字典中的单词。
        示例 3：

        输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
        输出: false


        提示：

        1 <= s.length <= 300
        1 <= wordDict.length <= 1000
        1 <= wordDict[i].length <= 20
        s 和 wordDict[i] 仅由小写英文字母组成
        wordDict 中的所有字符串 互不相同
        */

public class Code139_wordBreak {

    /**
     * 检查字符串s是否可以由字典wordDict中的单词连续拼接而成
     *
     * @param s 输入的字符串
     * @param wordDict 字典，包含可用来拼接的单词
     * @return 如果s是由字典中的单词拼接而成，返回true；否则返回false
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        // 将字典转换为HashSet以提高查找效率
        HashSet<String> wordSet = new HashSet<>(wordDict);
        int length = s.length();
        // dp数组，dp[i]表示s的前i个字符能否被拆分成字典中的单词
        boolean[] dp = new boolean[length + 1];
        // 如果输入字符串为空，则认为是可以由字典中的单词拼接而成
        dp[0] = true;
        for (int i = 1; i <= length; i++) {
            for (int j = 0; j < i; j++) {
                // 如果s的前j个字符可以被拆分，并且s从j到i的子串在字典中
                if (dp[j] && wordSet.contains(s.substring(j, i))) {
                    // 则s的前i个字符也可以被拆分
                    dp[i] = true;
                    // 不需要继续检查更大的j，因为已经找到一个拆分方式
                    break;
                }
            }
        }
        return dp[length];
    }

    public static void main(String[] args) {
        String s = "012345";
        System.out.println(s.substring(1,3));
    }
}
